//+------------------------------------------------------------------+
//|                                                        Stack.mqh |
//|                             Copyright 2000-2025, MetaQuotes Ltd. |
//|                                             https://www.mql5.com |
//+------------------------------------------------------------------+
#include <Generic/Interfaces/ICollection.h>    // 继承集合接口 ICollection<T>，获取基础集合能力
#include <Generic/Internal/ArrayFunction.h>    // 内部数组操作工具（复制、扩容、查找等底层实现）
#include <Generic/Internal/EqualFunction.h>    // 内部相等性判断工具（处理元素相等逻辑）

//+------------------------------------------------------------------+
//| CStack<T> 类：基于动态数组实现的栈（LIFO 后进先出）               |
//| 核心定位：实现 ICollection<T> 接口，采用“动态数组”作为底层存储，   |
//|           遵循 LIFO（Last-In-First-Out）原则，支持高效的栈顶操作    |
//| 核心特性：                                                      |
//|  1. LIFO 规则：最后入栈的元素最先出栈（类似“叠盘子”，只能从顶部取放）； |
//|  2. 动态扩容：栈满时自动翻倍扩容（初始容量4，避免频繁内存分配）；    |
//|  3. 高效操作：入栈（Push）、出栈（Pop）、查看栈顶（Peek）均为 O(1)；  |
//|  4. 随机访问弱：不支持按索引直接访问栈中间元素，查找/删除中间元素需 O(n)； |
//| 适用场景：所有需要按“后进先出”顺序处理数据的场景，典型如：          |
//|  - 函数调用栈（记录程序执行上下文，递归调用时自动压栈/出栈）；        |
//|  - 表达式求值（如逆波兰表达式计算，运算符与操作数按顺序压栈）；      |
//|  - 撤销操作（如文本编辑器的“Ctrl+Z”，每步操作压栈，撤销时出栈恢复）； |
//|  - 括号匹配（遍历字符串时，左括号压栈，右括号与栈顶匹配后出栈）；    |
//|  - 临时缓存（仅需访问最新添加的数据，如最近打开的文件列表）；        |
//+------------------------------------------------------------------+
template<typename T>
class CStack : public ICollection<T>
  {
protected:
   T                 m_array[];           // 底层动态数组（存储栈元素，栈底→数组[0]，栈顶→数组[m_size-1]）
   int               m_size;              // 当前栈中的有效元素数量（≥0，空栈时为0）
   const int         m_default_capacity;  // 默认初始容量（固定为4，栈空时首次压栈会初始化数组）

public:
   //----------------------------------------------------------------
   // 构造与析构接口
   //----------------------------------------------------------------
   /**
    * @brief 默认构造函数：创建空栈，使用默认初始容量（4）
    * @note 初始状态：数组未分配内存（首次 Push 时自动初始化），m_size=0
    */
                     CStack(void);

   /**
    * @brief 指定容量构造函数：创建空栈，使用自定义初始容量（取指定值与默认容量的较大值）
    * @param capacity [in] 自定义初始容量（≥0，若小于4则自动使用默认容量4）
    * @example 预期最多存储100个元素 → CStack<Order>(100)，避免多次扩容
    */
                     CStack(const int capacity);

   /**
    * @brief 从集合构造：创建栈并复制指定集合的所有元素（集合元素按顺序依次压栈）
    * @param collection [in] 源集合（实现 ICollection<T> 接口，如 ArrayList/HashSet）
    * @note 集合中索引0的元素成为栈底，最后一个元素成为栈顶（与集合遍历顺序一致）
    */
                     CStack(ICollection<T>* collection);

   /**
    * @brief 从数组构造：创建栈并复制指定数组的所有元素（数组元素按索引顺序依次压栈）
    * @param array [in] 源数组（元素类型与 T 一致）
    * @note 数组[0] → 栈底，数组[ArraySize-1] → 栈顶（与数组索引顺序一致）
    */
                     CStack(T &array[]);

   /**
    * @brief 析构函数：清理栈资源
    * @note MQL5 自动管理动态数组内存，无需手动释放 m_array，仅重置内部状态
    */
                    ~CStack(void);

   //----------------------------------------------------------------
   // 元素入栈接口
   //----------------------------------------------------------------
   /**
    * @brief 入栈操作（继承自 ICollection<T> 接口，等价于 Push()）
    * @param value [in] 待入栈的元素（类型与 T 一致）
    * @return bool - 入栈结果：true=入栈成功；false=入栈失败（仅当内存不足时可能失败）
    * @note 内部调用 Push() 实现，元素添加到栈顶
    */
   bool              Add(T value);

   /**
    * @brief 入栈操作：将元素添加到栈顶（核心入栈方法）
    * @param value [in] 待入栈的元素（类型与 T 一致）
    * @return bool - 入栈结果：true=入栈成功；false=入栈失败（内存不足导致数组扩容失败）
    * @note 栈满时自动翻倍扩容（如容量4→8→16...），确保入栈成功（除非内存耗尽）
    */
   bool              Push(T value);

   //----------------------------------------------------------------
   // 栈信息与状态检查接口
   //----------------------------------------------------------------
   /**
    * @brief 获取栈中的有效元素数量（继承自 ICollection<T> 接口）
    * @return int - 元素数量（≥0，空栈返回0）
    */
   int               Count(void);

   /**
    * @brief 检查栈是否包含指定元素
    * @param item [in] 待检查的元素（类型与 T 一致）
    * @return bool - 检查结果：true=包含该元素；false=不包含
    * @note 内部从栈顶向栈底线性遍历查找，时间复杂度 O(n)（栈不适合频繁查找中间元素）
    */
   bool              Contains(T item);

   /**
    * @brief 缩减栈容量至实际元素数量（仅当元素数量小于当前容量的90%时生效）
    * @note 用途：释放未使用的内存（如栈从100个元素缩减到20个，容量从128缩为20）
    *       逻辑：若 m_size < (当前容量 * 0.9)，则将数组容量设为 m_size
    */
   void              TrimExcess(void);

   //----------------------------------------------------------------
   // 元素复制接口
   //----------------------------------------------------------------
   /**
    * @brief 将栈中的所有元素按“栈顶→栈底”顺序复制到外部数组（继承自 ICollection<T> 接口）
    * @param dst_array [out] 目标数组（需提前分配空间，或由方法自动扩容）
    * @param dst_start [in] 目标数组的起始复制索引（默认从0开始）
    * @return int - 实际复制的元素数量（等于 Count()，空栈返回0）
    * @note 复制顺序：栈顶元素 → 数组[dst_start]，栈底元素 → 数组[dst_start+Count-1]（与出栈顺序一致）
    */
   int               CopyTo(T &dst_array[], const int dst_start=0);

   //----------------------------------------------------------------
   // 元素出栈与清理接口
   //----------------------------------------------------------------
   /**
    * @brief 清空栈：删除所有元素，重置栈状态（继承自 ICollection<T> 接口）
    * @note 清空后：数组内存保留（仅填充0值），m_size=0，下次 Push 可直接复用数组
    */
   void              Clear(void);

   /**
    * @brief 从栈中删除首次出现的指定元素（非LIFO规则，需谨慎使用）
    * @param item [in] 待删除的元素（类型与 T 一致）
    * @return bool - 删除结果：true=删除成功（找到元素并移除）；false=删除失败（元素不存在）
    * @note 注意：此操作破坏栈LIFO特性，需移动后续元素填补空位，时间复杂度 O(n)
    */
   bool              Remove(T item);

   //----------------------------------------------------------------
   // 栈顶元素访问接口
   //----------------------------------------------------------------
   /**
    * @brief 查看栈顶元素（不删除，仅返回值）
    * @return T - 栈顶元素值
    * @warning 栈空时返回值未定义（建议先通过 Count() > 0 判断栈非空）
    */
   T                 Peek(void);

   /**
    * @brief 出栈操作：移除并返回栈顶元素（核心出栈方法）
    * @return T - 出栈的栈顶元素值
    * @warning 栈空时返回值未定义（建议先通过 Count() > 0 判断栈非空）
    * @note 出栈后 m_size 自动减1，数组未使用部分暂不释放（下次入栈可复用）
    */
   T                 Pop(void);
  };
//+------------------------------------------------------------------+